6.2 深度优先搜索与广度优先搜索
图是一个重要的数据结构，而遍历图的方式主要有两种：深度优先搜索 和 广度优先搜索。这两种算法分别适合不同的场景。
本节我们将介绍 深度优先 和 广度优先 搜索的基本概念、算法原理，并使用 Go 语言实现它们。
本节代码存放目录为 lesson13
概念与原理
深度优先搜索（DFS）
深度优先搜索 是一种沿着图的某一路径一直搜索到底的算法。当遇到某个顶点无法继续前进时，算法会回溯到上一个顶点，并尝试其他路径。
简单理解，DFS 就像是在迷宫中尽可能走到底，如果无法继续就回退，再走其他路径。
深度优先搜索算法步骤如下：
从起始顶点开始，访问该顶点并标记为已访问。
选择该顶点的一个未访问邻接顶点，递归访问该顶点。
如果当前顶点的所有邻接顶点都已访问，回退到前一个顶点，继续搜索未访问的顶点。
重复上述步骤，直到所有顶点都被访问。
DFS 示例如下
我们使用如下图结构示意 DFS 的遍历方式：
图结构：
A --- B
| |
C --- D
\
E
从顶点 A 开始执行 DFS，遍历顺序为：
A -> B -> D -> C -> E
广度优先搜索（BFS）
广度优先搜索 是一种逐层搜索的算法，先访问某个顶点，然后再访问它的所有邻接顶点，接着依次访问这些邻接顶点的邻接顶点。
简单理解，BFS 就像是一层一层地涂满每个节点，不断扩展访问范围，直到所有节点都被访问。
广度优先搜索算法步骤如下：
从起始顶点开始，访问该顶点并标记为已访问。
将该顶点的所有未访问邻接顶点添加到队列中。
从队列中取出第一个顶点，访问并标记为已访问。
重复步骤
2和3，直到队列为空，即所有顶点都被访问。
BFS 示例如下：
同样使用如下图结构示意 BFS 的遍历方式：
图结构：
A --- B
| |
C --- D
\
E
从顶点 A 开始执行 BFS，遍历顺序为：
A -> B -> C -> D -> E
总的来说，深度优先搜索就是沿着一条线一直搜到底，如果没有就回到上一个顶点接着再一直搜到底；而广度优先搜索则是全面的推进，一层一层的往下搜索。
深度优先搜索与广度优先搜索的区别如下
DFS 适用于：
搜索深度未知的问题。
需要找到所有路径或所有解的场景。
BFS 适用于：
搜索广度未知的问题。
需要找到最短路径或最优解的场景。
DFS 是深度优先，所以可能先深入图的某条路径后再回溯；BFS 是逐层搜索，所以能够保证先找到最短路径。
Go 语言的实现
深度优先搜索
在 Go 语言中，我们可以使用递归来实现 DFS。
// Graph 定义图结构，使用邻接表
type Graph struct {
// 图结构
vertices map[string][]string
// 已访问的节点
visited map[string]bool
}
// NewGraph 创建一个新的图
func NewGraph() *Graph {
return &Graph{
vertices: make(map[string][]string),
visited: make(map[string]bool),
}
}
// AddEdge 添加五向边
func (g *Graph) AddEdge(v1, v2 string) {
g.vertices[v1] = append(g.vertices[v1], v2)
g.vertices[v2] = append(g.vertices[v2], v1)
}
// DFS 实现深度优先搜索
func (g *Graph) DFS(v string) {
// 标记为已访问
g.visited[v] = true
fmt.Printf("%s", v)
// 递归访问所有未访问的节点
for _, neighbor := range g.vertices[v] {
// 未访问过
if !g.visited[neighbor] {
g.DFS(neighbor)
}
}
}
// ClearDFS 清除搜索标记
func (g *Graph) ClearDFS() {
g.visited = make(map[string]bool)
}
func main() {
// 创建图
graph := NewGraph()
graph.AddEdge("A", "B")
graph.AddEdge("A", "C")
graph.AddEdge("B", "D")
graph.AddEdge("C", "E")
graph.AddEdge("D", "C")
graph.AddEdge("E", "A")
fmt.Println("深度优先搜索结果：")
// 从 A 开始深度优先搜索
graph.DFS("A")
graph.ClearDFS()
fmt.Println()
// 从 B 开始深度搜索
graph.DFS("B")
}
执行结果输出如下所示：
深度优先搜索结果：
ABDCE
BACED
广度优先搜索
在 Go 语言中，我们可以使用队列来实现 BFS。
// Graph 定义图结构，使用邻接表
type Graph struct {
// 图结构
vertices map[string][]string
}
// NewGraph 创建一个新的图
func NewGraph() *Graph {
return &Graph{
vertices: make(map[string][]string),
}
}
// AddEdge 添加五向边
func (g *Graph) AddEdge(v1, v2 string) {
g.vertices[v1] = append(g.vertices[v1], v2)
g.vertices[v2] = append(g.vertices[v2], v1)
}
// BFS 实现广度优先搜索
func (g *Graph) BFS(start string) {
// 创建队列
queue := list.New()
// 存储访问过的节点
visited := make(map[string]bool)
// 初始化队列，将起始节点入队
queue.PushBack(start)
visited[start] = true
// 循环处理队列中的节点
for queue.Len() > 0 {
// 出队
element := queue.Front()
v := element.Value.(string)
queue.Remove(element)
fmt.Printf("%s ", v)
// 访问邻接节点
for _, neighbor := range g.vertices[v] {
if !visited[neighbor] {
queue.PushBack(neighbor)
visited[neighbor] = true
}
}
}
}
func main() {
// 创建图
graph := NewGraph()
graph.AddEdge("A", "B")
graph.AddEdge("A", "C")
graph.AddEdge("B", "D")
graph.AddEdge("C", "E")
graph.AddEdge("D", "C")
graph.AddEdge("E", "A")
fmt.Println("广度优先搜索结果：")
// 从 A 开始广度优先搜索
graph.BFS("A")
fmt.Println()
// 从 B 开始广度优先搜索
graph.BFS("B")
}
执行结果输出如下所示：
广度优先搜索结果：
A B C E D
B A D C E
小结
本节我们针对深度优先搜索、广度优先搜索的基本概念以及Go语言的实现进行了讲解。
关于本节总结如下：
深度优先搜索采用递归方式深入图的某条路径，适合用于找到所有解或路径。广度优先搜索采用队列逐层搜索，适合用于找到最优解或最短路径。